#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"

void Swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}
// 冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j+1])
			{
				Swap(a + j, a + j+1);
			}
		}
	}
}

// 快速排序递归实现
// 快速排序hoare版本

int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	left++;
	while (left <= right)
	{
		//begin从左往右找大
		while (left <= right && a[left] < a[keyi])
		{
			left++;
		}
		//end从右往左找小
		while (left <= right && a[right] > a[keyi])
		{
			right--;
		}
		if(left <= right)
			Swap(a + left++, a + right--);
	}
	Swap(a + right, a + keyi);
	return right;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
	int hole = left;
	int keyi = a[hole];
	int begin = hole;
	int end = right;
	while (begin < end)
	{
		//end从右向左找小
		while (begin < end && a[end] > keyi)
		{
			end--;
		}
		//填坑
		a[hole] = a[end];
		//设置新的坑
		hole = end;
		//begin从左到右找大
		while (begin < end && a[begin] < keyi)
		{
			begin++;
		}
		a[hole] = a[begin];
		hole = begin;
	}
	a[hole] = keyi;
	return hole;
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
	int keyi = a[left];
	int pcur = left;
	int next = left + 1;
	while (next <= right)
	{
		if (a[next] < keyi && ++pcur != next)
		{
			Swap(a + pcur, a + next);
		}
		next++;
	}
	Swap(a + left, a + pcur);
	return pcur;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi+1, right);
}

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	//栈的初始化
	StackInit(&st);
	//入栈right
	StackPush(&st, right);
	//入栈left
	StackPush(&st, left);
	//判断栈是否为空
	while (!StackEmpty(&st))
	{
		//取栈顶元素 - left
		int begin = StackTop(&st);
		//出栈
		StackPop(&st);
		//取栈顶元素 - right
		int end = StackTop(&st);
		//出栈
		StackPop(&st);

		//找基准值
		int prev = begin;
		int cur = begin + 1;
		int keyi = begin;
		while (cur <= end)
		{
			if (a[cur] < a[keyi] && ++prev != cur)
			{
				Swap(a + cur, a + prev);
			}
			cur++;
		}
		Swap(a + prev, a + keyi);
		keyi = prev;
		//左区间:left keyi-1
		//右区间:keyi+1 right
		//区间有效才能入栈,一个元素不如栈
		if (keyi - 1 > begin)
		{
			//入栈
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
		if (keyi + 1 < end)
		{
			//入栈
			StackPush(&st,right);
			StackPush(&st, keyi + 1);

		}
	}
	//栈的销毁
	StackDestroy(&st);
}

void arrPrint(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void StakcTest()
{
	ST st;
	//栈的初始化
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	printf("%d ", StackSize(&st));
	bool StackData = StackEmpty(&st);
	printf("%d", StackData);
	//栈的销毁
	StackDestroy(&st);

}

int main()
{
	int arr[] = { 4,6,5,9,1,3,2,8,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//BubbleSort(arr, sz);
	//QuickSort(arr, 0,sz-1);
	QuickSortNonR(arr, 0,sz-1);
	arrPrint(arr, sz);
	//StakcTest();
	return 0;
}